package com.lm.leetcode.str;

import com.lm.leetcode.PrintUtils;

/**
 * @Auther: Min.Liu
 * @Description: 给你两个字符haystack 和 needle ，
 * 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果needle 不是 haystack 的一部分，则返 -1 。
 *
 *   对KMP算法的直接应用
 * @Date: Created in 14:37 2025/5/9
 */
public class strStrDemo {
    public static void main(String[] args) {
        strStrDemo demo = new strStrDemo();
//        System.out.println(demo.strStr("ACTGPACTGKACTGPACY", "ACTGPACY"));
        System.out.println(demo.strStr("sadbutsad", "sad"));
    }

    public int strStr(String s, String p) {
        int ls = s.length(), lp = p.length(), i = 0, j = 0;
        int[] next = new int[lp];
        getNextArray(p, next);//获取关于模式串p的next数组
        while(i < ls && j < lp) {
            if(s.charAt(i) == p.charAt(j)) {
                ++i;
                ++j;
            /*
            如果模式串p的第一个字符p[0]和字符串s的当前字符s[i]都不匹配，
            那么说明s中从i开始不可能匹配出p来，因此换下一个开头继续尝试
            */
            }else if(j == 0) ++i;

            /*
            否则j位置不是0，说明它前面有匹配成功的部分，
            那么此时j应该调整为next[j]的位置
            */
            else j = next[j];
        }

        return j == lp?i-j:-1;
    }

    //生成next数组
    private static void getNextArray(String p, int[] next) {
        int len = p.length();
        next[0] = -1;
        if(len == 1) return;
        next[1] = 0;

        //i: 当前要求解next[i]
        //cn: cn始终记录next[i - 1]的值
        // A C T G P A C Y
        //-1 0
        int i = 2, cn = next[i - 1];
        while(i < len) {
            if(p.charAt(i - 1) == p.charAt(cn)) next[i++] = ++cn;
            else if(cn == 0) next[i++] = 0;
            else cn = next[cn];
        }
    }

}
